#include"MergeSort.h"

void mergeSort(vector<int> & arr)
{
	vector<int> tmpArr(arr.size());

	mergeSort(arr, tmpArr, 0, arr.size() - 1);
}

void mergeSort(vector<int> & arr, vector<int> & tmparr, int lbegin, int rend)
{
	cout << "sort pos: " << lbegin << " - " << rend << endl;

	if (lbegin < rend)
	{
		int center = (lbegin + rend) / 2;

		mergeSort(arr, tmparr, lbegin, center);
		mergeSort(arr, tmparr, center + 1, rend);
		merge(arr, tmparr, lbegin, center + 1, rend);
	}
}


void merge(vector<int> & arr, vector<int> & tmparr, int lbegin, int rbegin, int rend)
{
	int lend = rbegin - 1;
	int tmppos = lbegin;
	int total = rend - lbegin + 1;

	while (lbegin <= lend && rbegin <= rend)
	{
		if (arr[lbegin] <= arr[rbegin])
			tmparr[tmppos++] = arr[lbegin++];
		else
		{
			tmparr[tmppos++] = arr[rbegin++];
		}
	}

	cout << "copy rest " << tmppos << endl;

	while (lbegin <= lend){
		cout << " temppos = " << tmppos << " lpos = " << lbegin << endl;
		tmparr[tmppos++] = arr[lbegin++];
	}
		
	while (rbegin <= rend)
	{
		cout << " temppos = " << tmppos << " rpos = " << rbegin << endl;
		tmparr[tmppos++] = arr[rbegin++];
	}
		


	cout << "copy all " << endl;
	for (int i = 0; i < total; ++i, rend--)
	{
		cout << "copy pos = " << rend << endl;
		arr[rend] = tmparr[rend];
	}
}